package cn.zhaoyuening.algorithms.tree;

import cn.zhaoyuening.algorithms.tree.core.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by Buynow on 2017/7/15.
 */
public class BFSDemo {

    public static void main(String[] args) {
        bfs(DemoTree.getDemoTree());
    }

    public static void bfs(TreeNode node) {
        //queue
        Queue<TreeNode> queue = new LinkedList<>();
        //mark
        TreeNode last = node;
        TreeNode nextLast = null;
        queue.add(node);
        pollQueue(queue,last,nextLast);

    }

    private static void pollQueue(Queue<TreeNode> queue,TreeNode last,TreeNode nextLast) {
        TreeNode pollNode = queue.poll();
        System.out.print(pollNode.getData()+" ");
        TreeNode leftNode = pollNode.getLeftNode();
        TreeNode rightNode = pollNode.getRightNode();
        int inQueueCount = 0;
        if (leftNode != null) {
            inQueueCount++;
            queue.add(leftNode);
            nextLast = leftNode;
        }
        if (rightNode != null) {
            inQueueCount++;
            queue.add(rightNode);
            nextLast = rightNode;
        }
        if (pollNode == last) {
            System.out.println();
            last = nextLast;
        }

        for (;inQueueCount>0;inQueueCount--) {
            pollQueue(queue, last, nextLast);
        }



    }
}
